package com.yuanzhi.train.str;

import java.util.*;

/**
 * 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
 *
 * 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
 *
 *
 *
 *  
 *
 * 示例 1：
 *
 * 输入：digits = "23" 输出：["ad","ae","af","bd","be","bf","cd","ce","cf"] 示例 2：
 *
 * 输入：digits = "" 输出：[] 示例 3：
 *
 * 输入：digits = "2" 输出：["a","b","c"]  
 *
 * 提示：
 *
 * 0 <= digits.length <= 4 digits[i] 是范围 ['2', '9'] 的一个数字。
 * 
 * @author yuanZhi
 * @since 2022/1/15 9:03
 */
public class LetterCombinations {
	private static final Map<Character, String> phoneNumStrMap = new HashMap<>();
	static {
		phoneNumStrMap.put('2', "abc");
		phoneNumStrMap.put('3', "def");
		phoneNumStrMap.put('4', "ghi");
		phoneNumStrMap.put('5', "jkl");
		phoneNumStrMap.put('6', "mno");
		phoneNumStrMap.put('7', "pqrs");
		phoneNumStrMap.put('8', "tuv");
		phoneNumStrMap.put('9', "wxyz");
	}

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		String digits = scanner.next();
		System.out.println(letterCombinations(digits));
	}

	private static List<String> letterCombinations(String digits) {
		List<String> combinations = new ArrayList<>();
		if (digits == null || digits.length() == 0) {
			return combinations;
		}
		backtrack(combinations, digits, 0, new StringBuilder());
		return combinations;
	}

	/**
	 * 回溯
	 * 
	 * 从第一个元素开始，所以最初index传0
	 */
	private static void backtrack(List<String> combinations, String digits,
			int index, StringBuilder combination) {
		if (index == digits.length()) {
			combinations.add(combination.toString());
		} else {
			char digit = digits.charAt(index);
			String letters = phoneNumStrMap.get(digit);
			int length = letters.length();
			for (int i = 0; i < length; i++) {
				combination.append(letters.charAt(i));
				backtrack(combinations, digits, index + 1, combination);
				// 回溯成功后删除该位置元素进入下一次循环再次回溯
				combination.deleteCharAt(index);
			}
		}
	}

}
